Embodiments of the invention relate to an apparatus or a method for calculating a result of a scalar multiplication of a reference number with a reference point on an elliptic curve.
The use of elliptic curves replaces more and more the RSA method (Rivest-Shamir-Adleman method) in public key cryptography systems. The cryptography for elliptic curves was proposed by V. Miller in “Victor S. Miller. Use of Elliptic Curves in Cryptography. In Hugh C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 417-426. Springer, 1985” and N. Koblitz in “Neil Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, 48:203-209, 1987”.
Introducing literature about elliptic curves and their cryptography are, for example, the textbooks “Henri Cohen and Gerhard Frey, editors. Handbook of Elliptic and Hyperelliptic curve Cryptography. Chapman & Hall/CRC, 2006,” and “Ian Blake, Gadiel Seroussi and Nigel Smart, Advances in Elliptic Curve Cryptography (London Mathematical Society Lecture Note Series). Cambridge University Press, New York, N.Y., USA, 2005.” A good short review article is, for example, “Alfred Menezes and Scott A. Vanstone, Elliptic Curve Cryptosystems and Their Implementations. J. Cryptology, 6(4):229-224, 1993”. Since elliptic curves were studied by mathematicians already in the 19th century and before, the general literature in this direction is unmanageable, but most of the time only readable by mathematicians.
While at RSA the crucial step for encrypting and decrypting or for generating a signature and verifying a signature is the exponention md mod N of a message m modulo a large number N, which is the product of two large and secret prime numbers, the crucial process of the elliptic curve cryptography is the scalar multiplication of a number with a point on the curve.
An elliptic curve E:=E(F) over a finite field F is a finite commutative (Abelian) group. The elements of this group are a solution of an equation of third grade in this field, for example:E(F)={(x,y)εF×F:y2=x3+ax+b}∪{0}or, more generally,E(F)={(x,y)εF×F:y2+dxy+ey=x3+ax2+cx+b}∪{0}wherein a, b, c, d, e are elements of F, which have to fulfill certain properties. Further, an artificial point O is added. On this set, an addition is defined, which means two points P, Q out of E(F) can be added (and also subtracted), so that a new point R=P+Q is created on this curve. The following laws are valid:    1. Associativity: (P+Q)+R=P+(Q+R).    2. The existence of an identity element: O+P=P.    3. The existence of the inverse elements (−P) to P, so that: (−P)+P=O.    4. Commutativity: P+Q=Q+P.
These laws make the elliptic curve to an Abelian group. In such a group, automatically a scalar multiplication kP is defined by:kP=P+P+. . . +P (k times)wherein k is an integer out of Z and P is a point on the curve. This scalar multiplication is the central operation in the elliptic curve cryptography. Most of the time, the scalar k is one of the secrets.
Therefore, the scalar multiplication has to be implemented in a secure way, so that the chance for finding out the scalar k, for example, by side channel attacks as SPA or DPA, by fault attacks or save error attacks, is as low as possible.
Side channel attacks are, for example, attacks on implementations of crypto systems, which use observations of timings, power consumption or electromagnetic radiation in order to obtain secret information that is originally supposed to be stored safely. In simple power analysis (SPA), an attacker directly observes a device's power consumption. For example, the amount of power consumed by the device varies depending on the data operated on and the instructions performed during different parts of an algorithm's execution.
Differential power analysis (DPA) exploits characteristic behavior (e.g., power consumption behavior of transistors and logic gates). DPA uses an attacking model and statistical analysis to extract hidden information from a large sample of power traces obtained during controlled cryptographic computation. The use of statistical methods in a controlled DPA environment allows identifying small differences in power consumption, which can be used, for example, to recover specific information, such as the individual bits in a secret key.
Fault attacks are, for example, computational save error attacks (C save error attacks) or memory save error attacks (M save error attacks). The computational save error attack may be developed by inducing any temporary random computational fault inside the arithmetic logic unit (ALU). A memory save error attack needs to induce a temporary memory fault inside a register or a memory location.
A secure implementation of this scalar multiplication in crypto systems as, for example, smart cards, PCs or other security products is of high importance. This includes a protection against, for example, side channel attacks, like SPA (simple power analysis) and DPA (differential power analysis), fault attacks and save error attacks.
For example, an easy method for implementing a scalar multiplication dP is the so-called Double-and-Add method:
input:  d=(dn−1 ... d1 d0)2 integer, P Point on curveoutput: d*PQ:= O;for (i:=n−1) to 0 by −1 do   Q ← 2*Q   if (di=1) then   Q ← Q+P  // now is Q = Di*P, Di=(dn−1 ... di+1 di)2   endendreturn Q
This is the most known method. Unfortunately it is not secure against SPA and DPA, because the doubling is usually calculated by other formulas than the addition of two points on the curve. These two processes can usually be monitored by the current characteristic and so the secret key can easily be determined.
Therefore a Double-and-always-Add method is often proposed:
input:  d=(dn−1 ... d1 d0)2 integer, P Point on curveoutput: d*PQ:= O;for (i:=n−1) to 0 by −1 do   Q ← 2*Q   if (di=1) then   Q ← Q+P   else   T ← Q+P   end   // now is Q = Di*P, Di=(dn−1 ... di+1 di)2endreturn Q
Hereby the current characteristic is balanced and such an attack is not possible anymore. On the other side, this implementation opens the door for save-error attacks (see for example “Sung-Ming Yen and Marc Joye. Checking Before Output May Not Be Enough Against Fault-Based Cryptoanalysis. IEEE Trans. Computers, 49(9):967-90, 2000”). Since the second path of the if/else instruction can be interrupt without changing the output, an attacker may extract information about the secret scalar out of this.
Both methods have also the drawback being not secure against DPA and other error attacks, if implemented naively.
A other method to get the SPA problem under control is the Montgomery ladder:
input:  d=(dn−1 ... d1 d0)2 integer, P Point on curveoutput: d*PQ0:= O; Q1:= P;for (i:=n−1) to 0 by −1 do   (Q1−di, Qdi) ← (Q0+Q1, 2*Qdi)   // now is Qb = (Di+b)*P, Di=(dn−1 ... di+1 di)2   endendreturn Q0
Here each round also consists of an addition and a doubling and is therefore secure against SPA. The DPA problem persists further on. This method may calculate the addition faster than other algorithms shown in “Wieland Fischer, Christophe Giraud, Erik Woodward Knudsen and Jean-Pierre Seifert. Parallel scalar multiplication on general elliptic curves over Fp hedged against Non-Differential Side-Channel Attacks. IACR, Cryptology ePrint Archive, (007), January 2007. Available at http://eprint.iacr.org/2002/007”, “Tetsuya Izu and Tsuyoshi Takagi. A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. In David Naccache and Pascal Paillier, editors Public Key Cryptography, volume 2274 of Lecture Notes in Computer Science, pages 280-296, Springer, 2002,” and “Marc Joye and Sung, Ming Yen, The Montgomery Powering Ladder. In Burton S. Kaliski Jr., C etin Kaya Ko c and Christof Paar, editors. Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, Calif., USA, Aug. 13-15, 2002, Revised Paper, volume 2523 of Lecture Notes in Computer Science, Springer, 2003, pages 291-302.”